import java.util.*;

public class tset {
    public static List<String> topKFrequent(String[] words, int k) {
        Map<String,Integer> map = new HashMap<>();
        //1、统计每个单词出现的次数
        int len = words.length;
        for(int i = 0;i < len;i++){
            if(map.containsKey(words[i])){
                int count = map.get(words[i]);
                count++;
                map.put(words[i],count);
            }else{
                map.put(words[i],1);
            }
        }
        //2、建立小根堆,指定比较的方式(如果频率相同，按照首字母大小排序)
        PriorityQueue<Map.Entry<String,Integer>> minHeap = new PriorityQueue<>(new Comparator<Map.Entry<String, Integer>>() {
            @Override
            public int compare(Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2) {
                if(o1.getValue() == o2.getValue()){
                    return o2.getKey().compareTo(o1.getKey());
                }
                return o1.getValue() - o2.getValue();
            }
        });
        //3、遍历map 调整优先级队列
        for(Map.Entry<String,Integer> tmp : map.entrySet()){
            if(minHeap.size() < k){
                minHeap.add(tmp);
            }else{
                Map.Entry<String,Integer> top = minHeap.peek();
                if(top.getValue().compareTo(tmp.getValue()) == 0){
                    if(top.getKey().compareTo(tmp.getKey()) > 0){
                        minHeap.poll();
                        minHeap.add(tmp);
                    }
                }else{
                    if(top.getValue().compareTo(tmp.getValue()) < 0){
                        minHeap.poll();
                        minHeap.add(tmp);
                    }
                }
            }
        }
        List<String> list = new ArrayList<>();
        for(int i = 0;i < k;i++){
            list.add(minHeap.poll().getKey());
        }
        Collections.reverse(list);
        return list;
    }

    public static void main(String[] args) {
        String[] words = new String[]{"i", "love", "leetcode", "i", "love", "coding"};
        String[] words2 = new String[]{"the", "day", "is", "sunny", "the", "the", "the", "sunny", "is", "is"};
        List<String> list= topKFrequent(words,2);
        List<String> list2= topKFrequent(words2,4);
        System.out.println(list);
        System.out.println(list2);
    }
}
